/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 * 
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
// 分离空闲链表+首次适配+立即合并
// 已分配的块需要记录大小 未分配的块需要记录大小和下一个空闲块的地址以及在尾部记录大小
// 对于每一个块指针的前一位，即记录位，最后一位当且仅当当前块的分配/空闲状态改变时改变，倒数第二位当且仅当前一个块的分配/空闲状态改变时改变
// 对于每一个块指针指向的位置，只有空闲块才有值，记录下一个空闲块的地址
// 对于每一个块的尾部，只有空闲块才有值，记录当前块的大小
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>

#include "mm.h"
#include "memlib.h"

/*********************************************************
 * NOTE TO STUDENTS: Before you do anything else, please
 * provide your team information in the following struct.
 ********************************************************/
team_t team = {
    /* Team name */
    "TJU",
    /* First member's full name */
    "Student",
    /* First member's email address */
    "student@tju.edu.cn",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""
};

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)


#define SIZE_T_SIZE (sizeof(size_t))
#define DSIZE (2 * SIZE_T_SIZE)
#define MIN_BLOCK_SIZE (4 * SIZE_T_SIZE)

#define GET_RECORD(p) (*(size_t *)((char *)(p) - SIZE_T_SIZE))
#define SET_RECORD(p, val) (*(size_t *)((char *)(p) - SIZE_T_SIZE) = (val))
#define GET_SIZE(p) (GET_RECORD(p) & ~0x7)
#define SET_SIZE(p, val) (SET_RECORD(p, (GET_RECORD(p) & 0x7) | (val)))
#define GET_WORD_PREV_PREV(p) (*(size_t *)((char *)(p) - DSIZE))
#define SET_WORD_PREV_PREV(p, val) (*(size_t *)((char *)(p) - DSIZE) = (val))
#define GET_WORD_NEXT(p) (*(size_t *)((char *)(p) + SIZE_T_SIZE))
#define SET_WORD_NEXT(p, val) (*(size_t *)((char *)(p) + SIZE_T_SIZE) = (val))
#define GET_BLOCK_TAIL(p) (*(size_t *)((char *)(p) + GET_SIZE(p) - DSIZE))
#define SET_BLOCK_TAIL(p, val) (*(size_t *)((char *)(p) + GET_SIZE(p) - DSIZE) = (val))
#define PTR_BLOCK_PREV(p) ((void *)((char *)(p) - GET_WORD_PREV_PREV(p)))
#define PTR_BLOCK_NEXT(p) ((void *)((char *)(p) + GET_SIZE(p)))
#define GET_PTR_LINK_NEXT(p) (*(void **)(p))
#define SET_PTR_LINK_NEXT(p, val) (*(void **)(p) = (val))
#define GET_CURR_TAG(p) (GET_RECORD(p) & 0x1)
#define SET_CURR_TAG(p, val) (SET_RECORD(p, (GET_RECORD(p) & ~0x1) | val))
#define GET_PREV_TAG(p) ((GET_RECORD(p) >> 1) & 0x1)
#define SET_PREV_TAG(p, val) (SET_RECORD(p, (GET_RECORD(p) & ~0x2) | (val << 1)))
#define GET_NEXT_TAG(p) (GET_RECORD((char *)(p) + GET_SIZE(p)) & 0x1)
#define SET_NEXT_TAG(p, val) (SET_RECORD((char *)(p) + GET_SIZE(p), (GET_RECORD((char *)(p) + GET_SIZE(p)) & ~0x2) | (val << 1)))

#define SEG_LEN 10
#define CHUNK_SIZE ((1 << 9) + (1 << 3))

// 已分配的块需要记录大小 未分配的块需要记录大小和下一个空闲块的地址以及在尾部记录大小
// 对于每一个块指针的前一位，即记录位，最后一位当且仅当当前块的分配/空闲状态改变时改变，倒数第二位当且仅当前一个块的分配/空闲状态改变时改变
// 对于每一个块指针指向的位置，只有空闲块才有值，记录下一个空闲块的地址
// 对于每一个块的尾部，只有空闲块才有值，记录当前块的大小

static void *data;
static void* *seg_list;
static int get_seg_index(size_t size);
static void *get_fit(size_t size);
static void *coalesce(void *free_block);
static void *extend_heap(size_t size);
static void insert_free_block(void *free_block);
static void delete_free_block(void *free_block);
static void *place(void *free_block, size_t size);

static int mm_check(void) {
    void *prev = data;
    void *p = (char *)prev + GET_SIZE(prev);
    // 遍历所有块，检查tag是否正确，检查是否有连续的两个空闲块，检查空闲块的尾部是否正确，检查空闲块是否在seg_list中
    while (GET_SIZE(p) != 0) {
        if (GET_CURR_TAG(p) != GET_NEXT_TAG(prev)) {
            printf("mm_check: tag error at %p\n%d %d\n", p, GET_CURR_TAG(p), GET_NEXT_TAG(prev));
            return -1;
        }
        if (GET_CURR_TAG(p) == 0 && GET_CURR_TAG(prev) == 0) {
            printf("mm_check: two free blocks at %p and %p\n", prev, p);
            return -1;
        }
        if (GET_CURR_TAG(p) == 0 && GET_BLOCK_TAIL(p) != GET_SIZE(p)) {
            printf("mm_check: tail error at %p\n", p);
            return -1;
        }
        if (GET_CURR_TAG(p) == 0) {
            int index = get_seg_index(GET_SIZE(p));
            void *q = seg_list[index];
            while (q != NULL && q != p) {
                q = GET_PTR_LINK_NEXT(q);
            }
            if (q == NULL) {
                printf("mm_check: free block not in seg_list at %p\n", p);
                return -1;
            }
        }
        prev = p;
        p = PTR_BLOCK_NEXT(p);
    }
    return 0;
}

/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    seg_list = (void **)mem_sbrk(SEG_LEN * SIZE_T_SIZE);
    if (seg_list == (void *)-1) {
        return -1;
    }
    for (int i = 0; i < SEG_LEN; i++) {
        seg_list[i] = NULL;
    }

    // 开头的块
    mem_sbrk(DSIZE);

    void *p = mem_sbrk(CHUNK_SIZE);
    if (p == (void *)-1) {
        return -1;
    }
    data = p;
    SET_SIZE(p, CHUNK_SIZE);
    SET_CURR_TAG(p, 0);
    SET_PREV_TAG(p, 1);
    SET_BLOCK_TAIL(p, CHUNK_SIZE);

    // 结尾的块
    void *epilogue = PTR_BLOCK_NEXT(p);
    SET_SIZE(epilogue, 0);
    SET_CURR_TAG(epilogue, 1);
    SET_PREV_TAG(epilogue, 0);

    insert_free_block(p);
    return 0;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size)
{
    // assert(mm_check() == 0);

    int newsize = ALIGN(size + SIZE_T_SIZE);
    
    // 对于小块，分配最小块
    if (newsize < MIN_BLOCK_SIZE) {
        newsize = MIN_BLOCK_SIZE;
    }

    // 遍历空闲块链表，找到合适的块
    void *p = get_fit(newsize);
    if (p == NULL) {
        // 没有合适的块，扩展堆
        p = extend_heap(newsize);
        if (p == NULL) {
            return NULL;
        }
    }
    return place(p, newsize);
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr)
{
    // assert(mm_check() == 0);

    // 标记当前块为空闲块然后合并
    SET_CURR_TAG(ptr, 0);
    SET_NEXT_TAG(ptr, 0);
    SET_BLOCK_TAIL(ptr, GET_SIZE(ptr));
    coalesce(ptr);
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    // assert(mm_check() == 0);

    if (ptr == NULL) {
        return mm_malloc(size);
    }
    if (size == 0) {
        mm_free(ptr);
        return NULL;
    }
    
    size_t newsize = ALIGN(size + SIZE_T_SIZE);
    if (newsize < MIN_BLOCK_SIZE) {
        newsize = MIN_BLOCK_SIZE;
    }
    size_t oldsize = GET_SIZE(ptr);

    if (oldsize == newsize) return ptr;
    else if (oldsize > newsize) {
        if (oldsize - newsize >= MIN_BLOCK_SIZE) {
            // 剩余空间足够大，分割块
            SET_SIZE(ptr, newsize);
            SET_BLOCK_TAIL(ptr, newsize);

            size_t remain_size = oldsize - newsize;
            void *new_next = PTR_BLOCK_NEXT(ptr);
            SET_SIZE(new_next, remain_size);
            SET_CURR_TAG(new_next, 0);
            SET_NEXT_TAG(new_next, 0);
            SET_PREV_TAG(new_next, 1);
            SET_BLOCK_TAIL(new_next, remain_size);
            coalesce(new_next);
            return ptr;
        } else {
            return ptr;
        }
    } else {
        void *next = PTR_BLOCK_NEXT(ptr);
        if (GET_CURR_TAG(next) == 0 && oldsize + GET_SIZE(next) >= newsize) {
            // 后面是空闲块，且合并后空间足够大
            delete_free_block(next);
            size_t all_size = oldsize + GET_SIZE(next);
            if (all_size - newsize >= MIN_BLOCK_SIZE) {
                SET_SIZE(ptr, newsize);
                SET_BLOCK_TAIL(ptr, newsize);
                size_t remain_size = all_size - newsize;
                void *new_next = PTR_BLOCK_NEXT(ptr);
                SET_SIZE(new_next, remain_size);
                SET_CURR_TAG(new_next, 0);
                SET_PREV_TAG(new_next, 1);
                SET_BLOCK_TAIL(new_next, remain_size);
                coalesce(new_next);
            } else {
                SET_SIZE(ptr, all_size);
                SET_BLOCK_TAIL(ptr, all_size);
                SET_NEXT_TAG(ptr, 1);
            }
            return ptr;
        } else if (GET_SIZE(next) == 0) {
            // 后面是结尾块，直接扩展堆
            void *new_ptr = mem_sbrk(newsize - oldsize);
            if (new_ptr == (void *)-1) {
                return NULL;
            }
            SET_SIZE(ptr, newsize);
            SET_NEXT_TAG(ptr, 1);

            void *epilogue = PTR_BLOCK_NEXT(ptr);
            SET_SIZE(epilogue, 0);
            SET_CURR_TAG(epilogue, 1);
            SET_PREV_TAG(epilogue, 1);

            return ptr;
        }
        else {
            // 只能重新分配内存
            void *new_ptr = mm_malloc(size);
            if (new_ptr == NULL) {
                return NULL;
            }
            memcpy(new_ptr, ptr, oldsize);
            mm_free(ptr);
            return new_ptr;
        }
    }
}

// 根据大小获取对应的链表索引
static int get_seg_index(size_t size) {
    if (size <= 16) {
        return 0;
    } else if (size <= 32) {
        return 1;
    } else if (size <= 64) {
        return 2;
    } else if (size <= 128) {
        return 3;
    } else if (size <= 256) {
        return 4;
    } else if (size <= 512) {
        return 5;
    } else if (size <= 1024) {
        return 6;
    } else if (size <= 2048) {
        return 7;
    } else if (size <= 4096) {
        return 8;
    } else {
        return 9;
    }
}

// 根据大小获取最小的满足大小的块
static void *get_fit(size_t size) {
    int index = get_seg_index(size);
    // 从最小的满足大小的块链表开始找
    for (int i = index; i < SEG_LEN; i++) {
        void *p = seg_list[i];
        while (p != NULL) {
            if (GET_SIZE(p) >= size) {
                return p;
            }
            p = GET_PTR_LINK_NEXT(p);
        }
    }
    return NULL;
}

// 合并空闲块
static void *coalesce(void *free_block) {
    size_t size = GET_SIZE(free_block);
    int prev_tag = GET_PREV_TAG(free_block);
    int next_tag = GET_NEXT_TAG(free_block);

    if (!prev_tag && !next_tag) {
        // 前后都是空闲块
        void *prev = PTR_BLOCK_PREV(free_block);
        void *next = PTR_BLOCK_NEXT(free_block);
        delete_free_block(prev);
        delete_free_block(next);
        size += GET_SIZE(prev) + GET_SIZE(next);
        SET_SIZE(prev, size);
        SET_BLOCK_TAIL(prev, size);
        insert_free_block(prev);
        return prev;
    } else if (!prev_tag && next_tag) {
        // 前面是空闲块
        void *prev = PTR_BLOCK_PREV(free_block);
        delete_free_block(prev);
        size += GET_SIZE(prev);
        SET_SIZE(prev, size);
        SET_BLOCK_TAIL(prev, size);
        insert_free_block(prev);
        return prev;
    } else if (prev_tag && !next_tag) {
        // 后面是空闲块
        void *next = PTR_BLOCK_NEXT(free_block);
        delete_free_block(next);
        size += GET_SIZE(next);
        SET_SIZE(free_block, size);
        SET_BLOCK_TAIL(free_block, size);
        insert_free_block(free_block);
        return free_block;
    } else {
        // 前后都不是空闲块
        insert_free_block(free_block);
        return free_block;
    }
}

// 插入空闲块
static void insert_free_block(void *free_block) {
    size_t size = GET_SIZE(free_block);
    SET_BLOCK_TAIL(free_block, size);
    int index = get_seg_index(size);
    void *p = seg_list[index];
    void *prev = NULL;

    // 先找到合适的位置，按地址排序
    while (p != NULL && p < free_block) {
        prev = p;
        p = GET_PTR_LINK_NEXT(p);
    }
    if (prev == NULL) {
        SET_PTR_LINK_NEXT(free_block, seg_list[index]);
        seg_list[index] = free_block;
    } else {
        SET_PTR_LINK_NEXT(prev, free_block);
        SET_PTR_LINK_NEXT(free_block, p);
    }
}

// 删除空闲块
static void delete_free_block(void *free_block) {
    size_t size = GET_SIZE(free_block);
    int index = get_seg_index(size);
    void *p = seg_list[index];
    void *prev = NULL;
    while (p != free_block && p != NULL) {
        prev = p;
        p = GET_PTR_LINK_NEXT(p);
    }
    // 未找到
    if (p == NULL) {
        assert(0);
    }
    if (prev == NULL) {
        seg_list[index] = GET_PTR_LINK_NEXT(free_block);
    } else {
        SET_PTR_LINK_NEXT(prev, GET_PTR_LINK_NEXT(free_block));
    }
}

// 扩展堆
static void *extend_heap(size_t size) {
    size_t new_size = ALIGN(size)>CHUNK_SIZE?ALIGN(size):CHUNK_SIZE;
    void *p = mem_sbrk(new_size);
    if (p == (void *)-1) {
        return NULL;
    }
    SET_SIZE(p, new_size);
    SET_CURR_TAG(p, 0);
    SET_BLOCK_TAIL(p, new_size);
    
    // 重新设置结尾的块
    void *epilogue = PTR_BLOCK_NEXT(p);
    SET_SIZE(epilogue, 0);
    SET_CURR_TAG(epilogue, 1);
    SET_PREV_TAG(epilogue, 0);

    return coalesce(p);
}

// 分配块
static void *place(void *free_block, size_t size) {
    size_t block_size = GET_SIZE(free_block);
    size_t remain_size = block_size - size;
    if (remain_size < MIN_BLOCK_SIZE) {
        // 剩余空间不足，整块分配
        SET_CURR_TAG(free_block, 1);
        SET_NEXT_TAG(free_block, 1);
        delete_free_block(free_block);
        return free_block;
    } else {
        if (size > 64) {
            if (size <= 128 && remain_size > MIN_BLOCK_SIZE * 2) {
                // 前面的块分配，后面的块空闲
                size += MIN_BLOCK_SIZE;
                remain_size -= MIN_BLOCK_SIZE;
                delete_free_block(free_block);
                SET_SIZE(free_block, size);
                SET_CURR_TAG(free_block, 1);
                SET_BLOCK_TAIL(free_block, size);
                void *next = PTR_BLOCK_NEXT(free_block);
                SET_SIZE(next, remain_size);
                SET_CURR_TAG(next, 0);
                SET_PREV_TAG(next, 1);
                SET_BLOCK_TAIL(next, remain_size);
                coalesce(next);
                return free_block;
            } else if (size <= 256 && remain_size > MIN_BLOCK_SIZE * 3) {
                // 前面的块分配，后面的块空闲
                size += MIN_BLOCK_SIZE * 2;
                remain_size -= MIN_BLOCK_SIZE * 2;
                delete_free_block(free_block);
                SET_SIZE(free_block, size);
                SET_CURR_TAG(free_block, 1);
                SET_BLOCK_TAIL(free_block, size);
                void *next = PTR_BLOCK_NEXT(free_block);
                SET_SIZE(next, remain_size);
                SET_CURR_TAG(next, 0);
                SET_PREV_TAG(next, 1);
                SET_BLOCK_TAIL(next, remain_size);
                coalesce(next);
                return free_block;
            } else if (size <= 512 && remain_size > MIN_BLOCK_SIZE * 5) {
                // 前面的块分配，后面的块空闲
                size += MIN_BLOCK_SIZE * 4;
                remain_size -= MIN_BLOCK_SIZE * 4;
                delete_free_block(free_block);
                SET_SIZE(free_block, size);
                SET_CURR_TAG(free_block, 1);
                SET_BLOCK_TAIL(free_block, size);
                void *next = PTR_BLOCK_NEXT(free_block);
                SET_SIZE(next, remain_size);
                SET_CURR_TAG(next, 0);
                SET_PREV_TAG(next, 1);
                SET_BLOCK_TAIL(next, remain_size);
                coalesce(next);
                return free_block;
            } else {
                // 前面的块空闲，后面的块分配
                delete_free_block(free_block);
                SET_SIZE(free_block, remain_size);
                SET_CURR_TAG(free_block, 0);
                SET_BLOCK_TAIL(free_block, remain_size);
                void *next = PTR_BLOCK_NEXT(free_block);
                SET_SIZE(next, size);
                SET_CURR_TAG(next, 1);
                SET_PREV_TAG(next, 0);
                SET_NEXT_TAG(next, 1);
                SET_BLOCK_TAIL(next, size);
                coalesce(free_block);
                return next;
            }
        } else {
            // 前面的块分配，后面的块空闲
            delete_free_block(free_block);
            SET_SIZE(free_block, size);
            SET_CURR_TAG(free_block, 1);
            SET_BLOCK_TAIL(free_block, size);
            void *next = PTR_BLOCK_NEXT(free_block);
            SET_SIZE(next, remain_size);
            SET_CURR_TAG(next, 0);
            SET_PREV_TAG(next, 1);
            SET_BLOCK_TAIL(next, remain_size);
            coalesce(next);
            return free_block;
        }
    }
}